§ 1.1 Field of the Invention
The present invention concerns rules used in communications networks, such as the provision of wildcard rules in the flow table (or more generally, a packet processing table) of a software defined network (“SDN”) switch.
§ 1.2 Background Information
Software-Defined Networking (SDN) enables network innovations and provides flexible flow control over network traffic. SDN proposes a variety of network policies for access control, traffic engineering, and energy efficiency to enhance the management of a communications network. These policies can be realized through the rules placed in the flow tables of SDN switches, such as open flow switches for example, to direct traffic forwarding.
Generally, a rule can be stored in the switch either as an exact-match rule (See, e.g., the article, M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker, “Rethinking Enterprise Network Control,” IEEE/ACM Transactions on Networking (TON), Vol. 17, No. 4, pp. 1270 1283 (2009), and the article, A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee Devoow, “Scaling Flow Management for High-Performance Networks,” ACM SIGCOMM Computer Communication Review, Vol. 41, pp. 254-265 (ACM, 2011), both incorporated herein by reference.) or a wildcard rule (See, e.g., the article, N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: Enabling Innovation in Campus Networks,” ACM SIGCOMM Computer Communication Review, Vol. 38, No. 2, pp. 69-74 (2008), and the article, M. Yu, J. Rexford, M. J. Freedman, and J. Wang, “Scalable Flow-Based Networking with Difane,” ACM SIGCOMM Computer Communication Review, Vol. 41, No. 4, pp. 351 362 (2011), both incorporated herein by reference.). Compared with exact-match rules, wildcard rules improve the reusability of rules in the flow table and reduce the number of flow setup requests to the controller, thereby enhancing the scalability of the system. However, wildcard rules are typically cached in Ternary Content Addressable Memory (“TCAM”), which is highly limited in capacity. The flow table in a commodity switch is reported to support only a few thousand wildcard rules. (See, e.g., the article, A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. Devoow, “Scaling Flow Management for High-Performance Networks,” ACM SIGCOMM Computer Communication Review, Vol. 41, pp. 254-265 (ACM, 2011), incorporated herein by reference.) To improve scalability, recent studies suggest either proactively allocating rules on multiple switches to load balance the flow table consumption (See, e.g., the article, M. Moshref, M. Yu, A. Sharma, and R. Govindan, “Scalable Rule Management for Data Centers,” Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation, pp. 157 170 (USENIX Association, 2013), incorporated herein by reference.) or reactively caching rules (See, e.g., the article, A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. Devoow, “Scaling Flow Management for High-Performance Networks,” ACM SIGCOMM Computer Communication Review, Vol. 41, pp. 254-265 (ACM, 2011), and the article, M. Yu, J. Rexford, M. J. Freedman, and J. Wang, “Scalable Flow-Based Networking with Difane,” ACM SIGCOMM Computer Communication Review, Vol. 41, No. 4, pp. 351 362 (2011), both incorporated herein by reference.) on each switch. Compared with proactive schemes, the reactive approach dynamically caches active rules in switches on demand, which saves flow table space and enables rapid reaction to traffic dynamics.
Reactively caching wildcard rules in switches creates several challenges. First, the cache miss rate needs to be controlled to improve network performance. Packets suffering from a cache miss will experience a 2-ms latency compared to a 5-ns latency with a cache hit. (See, e.g., the article, A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. Devoow, “Scaling Flow Management for High-Performance Networks,” ACM SIGCOMM Computer Communication Review, Vol. 41, pp. 254-265 (ACM, 2011), incorporated herein by reference.) A high cache miss rate also invokes frequent requests to the controller, and therefore causes control network bandwidth to be consumed. Second, dependency between rules complicates the caching process. More specifically, since rules with different priorities might overlap in field space, simply caching the requested rule can generate false packet forwarding (or more generally, erroneous packet processing). (See, e.g., the article, M. Yu, J. Rexford, M. J. Freedman, and J. Wang, “Scalable Flow-Based Networking with Difane,” ACM SIGCOMM Computer Communication Review, Vol. 41, No. 4, pp. 351 362 (2011), incorporated herein by reference.) Extra storage overhead may be used to guarantee the semantic correctness of rules cached in switches. Unfortunately, however, this increases the chance of flow table overflow.